package com.study.daily.algozuo.y2021.m12.day1201;

/**
 * ManWalk
 *
 * @author Tom on 2021/12/1
 */
public class Code01_ManWalk {
    public static void main(String[] args) {
        Code01_ManWalk cm = new Code01_ManWalk();
        System.out.println(cm.ways1(1, 4, 3, 6));
        System.out.println(cm.ways2(1, 4, 3, 6));
        System.out.println(cm.ways3(1, 4, 3, 6));
    }

    public int ways1(int start, int K, int aim, int N){
        return process1(start, K, aim, N);
    }
    public int process1(int cur, int rest, int aim,int N){
        if(rest == 0){
            return aim == cur ? 1 : 0;
        }
        if(cur == N){
            return process1(N - 1, rest - 1, aim, N);
        }
        if(cur == 1){
            return process1(2, rest - 1, aim, N);
        }
        // 來到了任意位置
        return process1(cur + 1, rest - 1, aim, N) + process1(cur - 1, rest - 1, aim, N);
    }
    public int ways2(int start, int K, int aim, int N){
        int[][] dp = new int[N+1][K+1];
        for(int i = 0; i < N+1; i++){
            for(int j = 0; j < K+1; j++){
                dp[i][j] = -1;
            }
        }
        return process2(start, K, aim, N, dp);
    }
    public int process2(int cur, int rest, int aim, int N, int[][] dp){
        if(dp[cur][rest] != -1){
            return dp[cur][rest];
        }
        int ans = 0;
        if(rest == 0){
            ans = aim == cur ? 1 : 0;
            dp[cur][rest] = ans;
        }else if(cur == N){
            ans = process2(N - 1, rest - 1, aim, N,dp);
            dp[cur][rest] = ans;
        } else if(cur == 1){
            ans = process2(2, rest - 1, aim, N, dp);
            dp[cur][rest] = ans;
        }else{
            ans = process2(cur + 1, rest - 1, aim, N, dp) + process2(cur - 1, rest - 1, aim, N,dp);
            dp[cur][rest] = ans;
        }
        // 來到了任意位置
        return ans;
    }

    public int ways3(int start, int K, int aim, int N){
        int[][] dp = new int[N+1][K+1];
        dp[aim][0] = 1;
        for(int col = 1; col < K + 1; col++){
            dp[1][col] = dp[2][col-1];
            for(int row = 2; row < N; row++){
                dp[row][col] = dp[row + 1][col - 1] + dp[row - 1][col - 1];
            }
            dp[N][col] = dp[N-1][col-1];
        }
        return dp[start][K];
    }
}
